// #include "tools.h"

// class Solution {
// public:
//      // [状态:pat.size()+1][当前字符]
//     //  https://www.cnblogs.com/labuladong/p/12320260.html
    

//     void set_pat(string pat){
//         int M = pat.size();
//         vector<vector<char>> dp(M, vector<char>(256, 0));

//         // 通过pat构建dp
//         dp[0][pat[0]] = 1;

//         int X = 0;
//         for(int j = 1; j < M; ++j){
//             for(char c = 0; c < 256; ++c){
//                 if(pat[j] == c)
//                     dp[j][c] = j + 1;   // 状态推进
//                 else
//                     dp[j][c] = dp[X][c];// 状态重启
//             }
//             // 更新影子状态
//             // 影子状态，与当前状态具有最长的相同前缀
//             X = dp[X][pat[j]];
//         }
        
//     }

//     int search(string txt){
//         /* 借助dp匹配txt */
//         int N = txt.size();

//         int j = 0; // pat 的初始态
//         for(int i = 0; i < N; ++i){
//             j = dp[j][txt[i]];
//             // 到达终止态
//             if(j == M) return i - M + 1;
//         }

//         return -1;
//     }
// };

// int main(int argc, char const *argv[])
// {
    
    
//     return 0;
// }
